{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4a191398",
   "metadata": {},
   "source": [
    "# Manipulation de liste\n",
    "\n",
    "Dans cette section, nous allons tenter de prendre un peu de distance avec Python et nous intéresser aux **algorithmes**. Un algorithme est tout simplement un ensemble d'étapes détaillées qui décrivent comment accomplir une tâche ou résoudre un problème. C'est comme un plan d'action détaillé, une idée qui doit ensuite être implémenter en Python.\n",
    "\n",
    "Nous allons donner quelques exemple d'algorithmes pour des taches élémentaires. Nous allons ensuite en donner les implémentations en Python.\n",
    "\n",
    "Nous commençons par des algorithmes simples pour aller faire d'autres plus avancés.\n",
    "\n",
    "\n",
    "## Recherche\n",
    "\n",
    "### Rechercher un élément dans une séquence\n",
    "\n",
    "Étant donnée une séquence, comment trouver s'il existe ou non, un élément donné ? Par exemple, pour la séquence suivante, `(7, 3, 5, 2, 4, 1, 8)`, comment déterminer si l'élément `2` est présent ?\n",
    "\n",
    "Bien évidement, nous allons devoir déterminer algorithme que l'on pourra implémenter en Python. Cela veut dire en particulier qu'il faut se **détacher du regard humain** que l'on peut avoir sur le problème et qui consiste à regarder la séquence dans sa globalité et ci répondre : \"bien évidemment, ça se voit\".\n",
    "\n",
    "Une bonne approche pour cela, est d'imaginer que pour Python, une séquence est livre avec une donnée inscrite sur chaque page. On ne peut pas regarder le livre dans globablité, la seule manière de procéder est de l'analyser en parcourant les pages les unes après les autres ou accédant à une page choisie à partir de son numéro. Dans se contexte, comment, pour un livre de plusieurs miliers de pages déterminer si une donnée est présente ou non ?\n",
    "\n",
    "Une approche que nous pourrions réaliser, serait de parcourir page après page le livre et regarder à chaque fois si la donnée recherchée est présente. Lorsqu'on trouve une telle page alors on peut répondre, \"oui, le livre contient bien la donnée\". Si après avoir parcouru toutes les pages, nous n'avons pas trouvé la donnée, alors \"non, le livre ne contient pas la donnée\". Cela correspond naturellement à l'algorithme de recherche d'une valeur dans une séquence.\n",
    "\n",
    "```\n",
    "Pour chaque valeur de la séquence\n",
    "    Si la valeur est celle recherchée\n",
    "        alors répondre oui\n",
    "Répondre non\n",
    "```\n",
    "\n",
    "Une fois cet algorithme posé, il devient relativement direct de le convertir en Python. On peut le faire avec une boucle pour, ou avec une boucle tant que. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2ef7e277",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rechercher(seq, elt):\n",
    "    for e in seq:\n",
    "        if e == elt:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "4feb122e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rechercher( (7, 3, 5, 2, 4, 1, 8), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "f997f7fc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rechercher( (7, 3, 5, 9, 4, 1, 8), 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af0c7325",
   "metadata": {},
   "source": [
    "Une version alternative avec la boucle tant que. Elle est un peu plus complexe car pour parcourir les valeurs de la séquence on doit gérer l'indice `i` à la main. On préfèrera donc la première méthode."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "7708981e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rechercher(seq, elt):\n",
    "    i = 0\n",
    "    while i < len(seq):\n",
    "        if seq[i] == elt:\n",
    "            return True\n",
    "        else:\n",
    "            i +=  1\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "b54c8a49",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rechercher( (7, 3, 5, 2, 4, 1, 8), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "9c3f9896",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rechercher( (7, 3, 5, 9, 4, 1, 8), 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04d3ec39",
   "metadata": {},
   "source": [
    "### Pourquoi ne pas utiliser `in ` ?\n",
    "\n",
    "Bien sur, une existe une manière plus simple de réaliser la recherche d'un élément dans une séquence. En python, c'est exactement ce que fait l'oppérateur `in`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "dbe5a510",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 in (7, 3, 5, 2, 4, 1, 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "c2b7303c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 in (7, 3, 5, 9, 4, 1, 8)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f5aa175",
   "metadata": {},
   "source": [
    "Pourtant cet algorithme de recherche est important, il faut être capable de le réaliser sans utiliser le mot clef `in` car il sera fréquent que soyez obligé de partir d'un algorithme de base et de l'adapter à vos besoins. Par exemple. Supposons que nous disposions de liste de villes suivantes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e0653c34",
   "metadata": {},
   "outputs": [],
   "source": [
    "villes = [('Paris', 48.859822979631595, 2.3424346745212903),\n",
    " ('Marseille', 43.3006443339931, 5.399212549333288),\n",
    " ('Lyon', 45.757556691319834, 4.840265609427432),\n",
    " ('Toulouse', 43.59682994774006, 1.4388269132731253),\n",
    " ('Nice', 43.706993704948886, 7.258872036700144),\n",
    " ('Nantes', 47.22695145891068, -1.5553965640676033),\n",
    " ('Montpellier', 43.61358641589052, 3.864199673082997),\n",
    " ('Strasbourg', 48.57698670737203, 7.749300150221324),\n",
    " ('Bordeaux', 44.84332596104577, -0.5809870763075933),\n",
    " ('Lille', 50.63004742852798, 3.0565319168675664)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "163d1e0c",
   "metadata": {},
   "source": [
    "Nous souhaitons savoir s'il existe une ville de coordonnées `47.23`, `-1.56`. Deux problèmes se posent.\n",
    " - Il est complexe, voir pénalisant d'utiliser l'oppérateur `in`.\n",
    " - Les coordonnées `47.23`, `-1.56` n'existent pas dans la liste de ville. En réalité, on voit que `('Nantes', 47.22695145891068, -1.5553965640676033)` est un bon candidat mais avec l'oppérateur `in`, on ne peut pas comparer `47.23` avec `47.22695145891068` ou `-1.56` avec `-1.5553965640676033`.\n",
    " \n",
    "Ce que nous pouvons faire par contre c'est adapter l'algorithme de recherche pour le faire fonctionner dans notre cas. Nous modifions la manière de dire quand un élément est égal à un autre. On recherche une ville dont la latitude et la longitude est à `0.1` de distance (en valeur absolue)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "830a6fc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rechercher_villes(villes, lat, lon):\n",
    "    for v in villes:\n",
    "        if abs(v[1]-lat) < 0.1 and abs(v[2]-lon) < 0.1:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2a8e250e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rechercher_villes(villes, 47.23, -1.56)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d73b29c",
   "metadata": {},
   "source": [
    "### Compter, trouver l'indice\n",
    "\n",
    "On peut adapter ce que l'on vient de voir pour faire des fonctions capable de compter le nombre d'occurence d'un élément ou rechercher l'indice de la première ou dernière occurence. Dans tous les cas, nous partons de l'algorithme de recherche et nous intégrons des petites modifications."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9df8e2b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compter_occurences(seq, elt):\n",
    "    nb = 0\n",
    "    for e in seq:\n",
    "        if e == elt:\n",
    "            nb +=  1\n",
    "    return nb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d132c5b1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compter_occurences( (7, 3, 2, 2, 4, 2, 8), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b168975c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rechercher_premiere_occurence(seq, elt):\n",
    "    for i in range(len(seq)):\n",
    "        if seq[i] == elt:\n",
    "            return i\n",
    "    return None # Attention, la valeur de retour n'est pas toujours un entier "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6bb01b52",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rechercher_premiere_occurence( (7, 3, 1, 2, 4, 2, 8), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8a184f62",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rechercher_derniere_occurence(seq, elt):\n",
    "    d = None\n",
    "    for i in range(len(seq)):\n",
    "        if seq[i] == elt:\n",
    "            d = i\n",
    "    return d # Attention, la valeur de retour n'est pas toujours un entier "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8dda44be",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rechercher_derniere_occurence( (7, 3, 1, 2, 4, 2, 8), 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c20ecea",
   "metadata": {},
   "source": [
    "## Rechercher un minimum\n",
    "\n",
    "Pour rechercher un minimum dans une séquence, on peut utiliser une variable pour stocker \"la plus petite valeur\" rencontrée. Ensuite, on parcours notre séquence et, pour chaque valeur, on la compare avec notre référence. Si la valeur est plus petite que la référence, on met à jour notre référence.\n",
    "\n",
    "```\n",
    "pt = la premiere valeur de la liste (par défaut)\n",
    "pour chaque élément e de la séquence\n",
    "    si e < pt\n",
    "        alors pt = e\n",
    "renvoyer pt\n",
    "```\n",
    "\n",
    "Ce qui donne en Python le code suivant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "9ed7d657",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum(seq):\n",
    "    pt = seq[0]\n",
    "    for e in seq:\n",
    "        if e < pt :\n",
    "            pt = e\n",
    "    return pt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "88b1afbc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minimum((7, 3, 1, 2, 4, 2, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "922b2e01",
   "metadata": {},
   "source": [
    "Bien sur, on peut vouloir récupérer non pas la valeut du plus petit élément mais son indice dans la séquence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7d141bc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def iminimum(seq):\n",
    "    pt = 0\n",
    "    for i in range(1, len(seq)): # On commence à 1 car pt vaut 0 par défaut.\n",
    "        if seq[i] < seq[pt] :\n",
    "            pt = i\n",
    "    return pt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "e6db8640",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iminimum((7, 3, 1, 2, 4, 2, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e2e99e5",
   "metadata": {},
   "source": [
    "En Python, il existe un raccourci pour cette oppération. Sur une séquence, on peut utiliser la fonction `min` (resp. `max`) qui renvoie la valeur du minimum (resp. maximum). Mais encore une fois, ici l'idée est de se familiariser avec ces algorithmes simples car vous allez devoir les reprendre et les adapter dans vos programmes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81b4c171",
   "metadata": {},
   "source": [
    "## Trier une liste\n",
    "\n",
    "Il existe un grand nombre d'algorithmes de tri. Nous commençons par un premier algorithme qui passe par la création d'une liste alternative. Ensuite nous proposerons deux algorithmes de tris dit \"en place\" c'est à dire qu'ils n'utilisent pas de seconde liste.\n",
    "\n",
    "### Créer une liste alternative\n",
    "\n",
    "Voici un premier algorithme qui prend en paramètre une liste `l1` et crée une liste `l2` avec le élément trié.\n",
    "```\n",
    "créer une nouvelle liste vide l2\n",
    "tant que la liste l1 n'est pas vide\n",
    "    pt = rechercher l'indice de l'élément le plus petit de l1\n",
    "    ajouter à la fin de l2, l'élément de l1 à l'indice pt\n",
    "    supprimer de l1 l'élément d'indice pt\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "d6ed6fb0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trier(l1):\n",
    "    l2 = []\n",
    "    while len(l1)>0:\n",
    "        pt = iminimum(l1)\n",
    "        l2.append( l1[pt] )\n",
    "        l1.pop(pt)\n",
    "    return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "ae4e14be",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trier( [7, 3, 1, 0, 4, 2, 8] )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cd3f99f",
   "metadata": {},
   "source": [
    "Cette fonction modifie la liste donnée en paramètre. C'est pas forcément idéal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "212846e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [7, 3, 1, 0, 4, 2, 8]\n",
    "l_ = trier(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "5111be4a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "b51528fa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0857ce10",
   "metadata": {},
   "source": [
    "Une première manière constite à dupliquer la liste donnée en paramètre. On ne la modifie donc pas. Il faut renvoyer la nouvelle liste triée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "564c66a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trier(l1):\n",
    "    l2 = []\n",
    "    l3 = l1[:] #copie de la liste\n",
    "    while len(l3)>0:\n",
    "        pt = iminimum(l3)\n",
    "        l2.append( l3[pt] )\n",
    "        l3.pop(pt)\n",
    "    return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "af22d4ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [7, 3, 1, 0, 4, 2, 8]\n",
    "l_ = trier(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "ed5582c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 3, 1, 0, 4, 2, 8]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l # n'est plus modifiée"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "b4d4b24b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7742def0",
   "metadata": {},
   "source": [
    "Une seconde manière de résoudre le problème consiste à remttre les éléments de la liste là où il était au début. Il est alors inutile de renvoyer une valeur puisque l'on modifie la liste passée en paramètre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "ea94658a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trier(l1):\n",
    "    l2 = []\n",
    "    while len(l1)>0:\n",
    "        pt = iminimum(l1)\n",
    "        l2.append( l1[pt] )\n",
    "        l1.pop(pt)\n",
    "    for e in l2:\n",
    "        l1.append(e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "9cb97496",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [7, 3, 1, 0, 4, 2, 8]\n",
    "trier(l)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "544e7d10",
   "metadata": {},
   "source": [
    "### Tri sélection\n",
    "\n",
    "Une manière plus classique est le tri à sélection. Il consiste à trouver le plus petit élément d'une liste, et à l'échanger avec le premier élément, puis à répéter cette opération pour la sous-liste commençant à partir du deuxième élément. Ce tri est \"en place\".\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "50759fe6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trier(l):\n",
    "    for i in range(len(l)-1):\n",
    "        # On recherche l'élément minimum dans la sous liste l[i:] qui a l'indice i dans la liste origiinale\n",
    "        pt = iminimum(l[i:])+i \n",
    "        l[i], l[pt] = l[pt], l[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "0eb7f95b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [7, 3, 1, 0, 4, 2, 8]\n",
    "trier(l)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe77fc14",
   "metadata": {},
   "source": [
    "### Tri à bulles\n",
    "\n",
    "Autre possiblité, le tri à bulles. Il consiste à parcourir la liste plusieurs fois en comparant les éléments adjacents et en les échangeant si nécessaire. Le nom \"tri à bulles\" vient du fait que les plus grandes valeurs \"flottent\" vers le haut de la liste comme des bulles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "d7204eeb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trier(l):\n",
    "    for _ in l:\n",
    "        for i in range(len(l)-1):\n",
    "            if l[i+1] < l[i]:\n",
    "                l[i], l[i+1] = l[i+1], l[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "28e5fe16",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [7, 3, 1, 0, 4, 2, 8]\n",
    "trier(l)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5762e8cc",
   "metadata": {},
   "source": [
    "Dans le pire des cas, le nombre de fois que l'on doit faire la boucle extérieur est égale à la longueur de la liste -1. Si la liste contient peu d'inversion, on peut s'arrêter avant. On obtient alors l'algorithme la fonction suivante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "37901cef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trier(l):\n",
    "    b = True\n",
    "    while b:\n",
    "        b = False\n",
    "        for i in range(len(l)-1):\n",
    "            if l[i+1] < l[i]:\n",
    "                l[i], l[i+1] = l[i+1], l[i]\n",
    "                b = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "74111b8c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 7, 8]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [7, 3, 1, 0, 4, 2, 8]\n",
    "trier(l)\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "515435ea",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}